package swardToOffer.struct_4_tree;

/**
 * @Author ChanZany
 * @Date 2021/5/21 19:08
 * @Version 1.0
 * 面试题28：对称的二叉树
 * 题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和
 * 它的镜像一样，那么它是对称的。
 * 思路：设计前序遍历的对称遍历算法，如果两种遍历方式下得到的序列相同，则说明是对称的
 * 注意：当子节点存在缺省即存在左子但不存在右子或者相反的情况下，得到的序列也是相同的，但是它不是对称二叉树
 * 所以需要把null节点考虑在内
 */
public class SymmetricalBinaryTree {
    boolean isSymmetrical(TreeNode root) {
        return helper(root, root);
    }

    private boolean helper(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        return helper(root1.left, root2.right) && helper(root1.right, root2.left);
    }

    public static void main(String[] args) {
        SymmetricalBinaryTree Main = new SymmetricalBinaryTree();
        TreeNode root = new TreeNode(7);
        TreeNode node1 = new TreeNode(7);
        TreeNode node2 = new TreeNode(7);
        TreeNode node11 = new TreeNode(7);
        TreeNode node12 = new TreeNode(7);
        TreeNode node21 = new TreeNode(7);
//        TreeNode node22 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node1.left = node11;
        node1.right = node12;
        node2.left = node21;
//        node2.right = node22;
        TreeUtil.preOrder(root);
        System.out.println(Main.isSymmetrical(root));
    }
}
